package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 21:53 2020/8/10
 * @Description 最长回文子序列
 * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
 * "bbbab"  输出4
 */


public class LongestPalindromeSubseq {
    /**
     * 可以使用动态规划来解决
     * i指向序列左边   j指向序列右边
     * 出口就是dp[0][n-1]
     * 如果s[i]==s[j]  dp[i][j] = d[i+1][j-1]+2
     * 如果s[i]!=s[j]  dp[i][j] = max(dp[i+1][j],dp[i][j-1])  这两个都是它上一步的值求最大
     * i==j时就是指向同一个元素，那它一定会是回文
     * i>j说明指针过界了就为0
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        // 每个元素自己都是长度为1的回文
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = 1;
        }
        int len = s.length();
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j <len;j++){
                if (s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len - 1];
    }
}
